package org.leetcode.hard.leetcode25;

import java.util.List;

public class Solution {

    public ListNode reverseKGroup3(ListNode head, int k) {

        int size = 0;

        ListNode temp = head;
        while (temp != null) {
            size++;
            temp = temp.next;
        }

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode preGroupEnd = dummy;

        ListNode pre = null;
        ListNode curr = head;
        ListNode next = null;

        for (int i = size; i >=k; i -= k) {
            int loopTimes = k;
            while (loopTimes>0){
                next = curr.next;
                curr.next=pre;
                pre = curr;
                curr = next;
                loopTimes--;
            }

            ListNode currGroupEnd = preGroupEnd.next;
            preGroupEnd.next=pre;
            currGroupEnd.next=curr;
            preGroupEnd=currGroupEnd;
        }

        return dummy.next;
    }


    public ListNode reverseKGroup2(ListNode head, int k) {

        if (k == 0 || k == 1) {
            return head;
        }

        int size = 0;
        ListNode temp = head;
        while (temp != null) {
            temp = temp.next;
            size++;
        }

        ListNode dummy = new ListNode(0, head);
        ListNode list = dummy;
        ListNode pre = null;
        ListNode curr = head;

        for (int i = size; i >= k; i = i - k) {
            //链表反转操作
            for (int j = 0; j < k; j++) {
                ListNode next = curr.next;
                curr.next = pre;
                pre = curr;
                curr = next;
            }
            //list表示为上一次反转后的链表的尾节点,要让list与这一次反转后的链表进行连接，所以让list.next=pre
            //end为反转后的尾节点
            //pre为当前翻转后的头节点
            //curr为下个没有翻转的链表的头节点
            ListNode end = list.next;
            list.next = pre;
            end.next = curr;
            list = end;
        }


        return dummy.next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode tail = head;

        for (int i = 0; i < k; i++) {
            if (tail == null) {
                return head;
            }

            tail = tail.next;
        }

        ListNode newHead = reverseList(head, tail);

        head.next = reverseKGroup(tail, k);

        return newHead;
    }


    private int getListLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }

        return length;
    }


    private ListNode reverseList(ListNode head, ListNode tail) {
        ListNode temp = null;
        ListNode prev = null;

        while (head != tail) {
            temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }

        return prev;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));


        solution.reverseKGroup(listNode, 2);
    }

}
